Thang Dinh, Ph.D.
Associate Professor
- Richmond VA UNITED STATES
- Engineering East Hall Room E4244
Computer scientist focusing on security and optimization challenges in complex systems including social networks.
Media
Social
Industry Expertise
Areas of Expertise
Accomplishments
Best-in-Session Presentation Award, INFOCOM 2016
INFOCOM'16 Presentation Award: Best-in-Session for Network Science 1
NVIDIA Hardware Grant Award 2016
NVIDIA Hardware donation
Best Paper Award, 4th Int. Conf. on Computational Social Networks, 2015
Best Paper Award, 4th Int. Conf. on Computational Social Networks, 2015
Outstanding International Student Award
2011
College of Engineering
University Alumni Fellowship Award
2008-2012
University of Florida
Distinguished Academic Achievement Award
2007
Vietnam National University
Honda Young Engineer and Scientist Award
2007
Honda Foundation and The National Institute for Science and Technology
Education
University of Florida
Ph.D.
Computer Engineering
2013
Vietnam National University
B.S.
Information Technology
2007
Selected Articles
Community Detection in Scale-free Networks: Approximation Algorithms for Maximizing Modularity
IEEE Journal on Selected Areas in Communications2013
Many networks, indifferent of their function and scope, converge to a scale-free architecture in which the degree distribution approximately follows a power law. Meanwhile, many of those scale-free networks are found to be naturally divided into communities of densely connected nodes, known as community structure. Finding this community structure is a fundamental but challenging topic in network science. Since Newman's suggestion of using modularity as a measure to qualify the strength of community structure, many efficient methods that find community structure based on maximizing modularity have been proposed. However, there is a lack of approximation algorithms that provide provable quality bounds for the problem. In this paper, we propose polynomial-time approximation algorithms for the modularity maximization problem together with their theoretical justifications in the context of scale-free networks. We prove that the solutions of the proposed algorithms, even in the worst-case, are optimal up to a constant factor for scale-free networks with either bidirectional or unidirectional links. Even though our focus in this work is not on designing another empirically good algorithms to detect community structure, experiments on real-world networks suggest that the proposed algorithm is competitive with the state-of-the-art modularity maximization algorithm.
On Centralized and Localized approximation algorithms for Interference-Aware Broadcast Scheduling
IEEE Transactions on Mobile Computing2013
Broadcast scheduling in multihop Wireless Sensor Networks (WSNs) is an effective mechanism to perform interference-aware broadcasting. Existing works provide centralized solutions, which cannot be implemented locally. Additionally, they consider very elementary network and interference models, in which, either all sensor nodes have the same transmission range or their transmission ranges are equal to their interference ranges that are not very practical. Furthermore, they entirely ignore the existence of WSNs in 3D. In this paper, we study the broadcast scheduling in 2D and 3D WSNs. We consider that sensor nodes may have different transmission ranges and their interference ranges are α times of their transmission ranges (where α >; 1). We devise efficient coloring methods for coloring a hexagonal tiling in 2D plane and a truncated octahedron tiling in 3D space, based on which we propose O(1)-centralized approximation algorithms and O(1)-localized approximation algorithms for the broadcast scheduling problem in 2D and 3D WSNs, respectively. Our O(1)-centralized approximation algorithms for 3D WSNs and O(1)-localized approximation algorithms for 2D and 3D WSNs are the first approximation algorithms for the corresponding problems. Finally, we present an efficient greedy heuristic to study the effect of various priority metrics for greedily scheduling multiple interfering transmissions. Theoretical analysis and experimental results are provided to evaluate the performance of our algorithms.
An Adaptive Approximation Algorithm for Community Detection in Dynamic Scale-free Networks
INFOCOM, 2013 Proceedings IEEE2013
We introduce A3CS, an adaptive framework with approximation guarantees for quickly identifying community structure in dynamic networks via maximizing Modularity Q. Our framework explores the advantages of power-law distribution property, is scalable for very large networks, and more excitingly, possesses approximation factors to ensure the quality of its detected community structure. To the best of our knowledge, this is the first framework that achieves approximation guarantees for the NP-hard modularity maximization problem, especially on dynamic networks. To certify our approach, we conduct extensive experiments in comparison with other adaptive methods on both synthesized networks with known community structures and real-world traces including ArXiv e-print citation and Facebook social networks. Excellent empirical results not only confirm our theoretical results but also promise the practical applicability of A3CS in a wide range of dynamic networks.
Maximizing the Spread of Positive Influence in Online Social Networks
Proceedings of the 33rd Int. Conf. on Distributed Computing Systems2013
Online social networks (OSNs) provide a new platform for product promotion and advertisement. Influence maximization problem arisen in viral marketing has received a lot of attentions recently. Most of the existing diffusion models rely on one fundamental assumption that an influenced user necessarily adopts the product and encourages his/her friends to further adopt it. However, an influenced user may be just aware of the product. Due to personal preference, neutral or negative opinion can be generated so that product adoption is uncertain. Maximizing the total number of influenced users is not the uppermost concern, instead, letting more activated users hold positive opinions is of first importance. Motivated by above phenomenon, we proposed a model, called Opinion-based Cascading (OC) model. We formulate an opinion maximization problem on the new model to take individual opinion into consideration as well as capture the change of opinions at the same time. We show that under the OC model, opinion maximization is NP-hard and the objective function is no longer submodular. We further prove that there does not exist any approximation algorithm with finite ratio unless P=NP. We have designed an efficient algorithm to compute the total positive influence based on this new model. Comprehensive experiments on real social networks are conducted, and results show that previous methods overestimate the overall positive influence, while our model is able to distinguish between negative opinions and positive opinions, and estimate the overall influence more accurately.
The Walls Have Ears: Optimize Sharing for Visibility and Privacy in Online Social Networks
Proceedings of the 21st ACM international conference on Information and knowledge management2012
With a rapid expansion of online social networks (OSNs), millions of users are tweeting and sharing their personal status daily without being aware of where that information eventually travels to. Likewise, with a huge magnitude of data available on OSNs, it poses a substantial challenge to track how a piece of information leaks to specific targets. In this paper, we study the problem of smartly sharing information to control the propagation of sensitive information in OSNs.
In particular, we formulate and investigate the Maximum Circle of Trust problem of which we seek to construct a circle of trust on the fly so that OSN users can safely share their information knowing that it will not be propagated to their unwanted targets (whom they are not willing to share with). Since most of messages in OSNs are propagated within 2 to 5 hops, we first investigate this problem under 2-hop information propagation by showing the hardness of obtaining an optimal solution, along with an algorithm with proven performance guarantee. In a general case where information can be propagated more than two hops, the problem is #P-hard i.e. the problem cannot be solved in a polynomial time. Thus we propose a novel greedy algorithm, hybridizing the handy but costly sampling method with a novel cut-based estimation. The quality of the hybrid algorithm is comparable to that of the sampling method while taking only a tiny fraction of the time. We have validated the effectiveness of our solutions in many real-world traces. Such an extensive experiment also highlights several important observations on information leakage which help to sharpen the security of OSNs in the future.